package chart.shortest_path;

import chart.图的存储.AbstractGraph;
import chart.图的存储.AdjacencyMatrix;
import chart.图的存储.Edge;

import java.util.Arrays;

/**
 * Floyd 算法
 * <p>求图中各个顶点间的最短路径</p>
 * <p>动态规划</p>
 * <p>时间复杂度: V^3</p>
 *
 * <p>算法要点：</p>
 * <p>邻接矩阵：存储顶点到其他顶点的距离</p>
 * <p>path[][]：path[i][j] 表示顶点 i 到顶点 j 的前驱顶点, 从 i 到 j, 先走到 k = path[i][j], 再看 path[k][j]</p>
 * <p>一个顶点到达另一个顶点, 不断地加入</p>
 *
 * @author yezh
 * @date 2023/7/13 9:15
 */
public class Floyd {

    public static void main(String[] args) {
        testAdjacencyMatrix();
    }

    private static void testAdjacencyMatrix() {
        AbstractGraph graph = new AdjacencyMatrix(6, false);
        graph.createGraph(Edge.graphDFS());
        floyd(graph);
    }

    public static void floyd(AbstractGraph graph) {
        int n = graph.getV();
        int[][] A = new int[n][n];
        int[][] path = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(A[i], Integer.MAX_VALUE);
            for (Edge edge : graph.getNeighborEdge(i))
                A[i][edge.getArcHead()] = edge.getWeigh();
            A[i][i] = 0;
            Arrays.fill(path[i], -1);
        }
        // 在顶点 i 到顶点 j 之间加入顶点 k
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++) {
                    if (A[i][k] != Integer.MAX_VALUE && A[k][j] != Integer.MAX_VALUE) {
                        int d = A[i][k] + A[k][j];
                        if (d < A[i][j]) {
                            A[i][j] = d;
                            path[i][j] = k;
                        }
                    }
                }
        for (int i = 0; i < n; i++) System.out.println(Arrays.toString(A[i]));
        System.out.println();
        for (int i = 0; i < n; i++) System.out.println(Arrays.toString(path[i]));
    }

}
